package com.example.java.yugutou.chapter1_linklist.level1;

/**
 * @Author : 佩萁
 * Description :
 * @Create : 2023/11/30 - 14:48
 */
class LinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addAtHead(1);
        list.addAtTail(2);
        list.addAtHead(3);
        list.printList(); // 输出应该是: 3 1 2
    }

    private Node dummyHead; // 虚拟头节点

    public LinkedList() {
        dummyHead = new Node(0); // 虚拟头节点的值通常不重要
    }

    class Node {
        int val;
        Node next;

        Node(int x) {
            val = x;
        }
    }

    // 插入一个节点到链表的头部（实际上是虚拟头节点之后）
    public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = dummyHead.next;//利用虚拟结点
        dummyHead.next = newNode;//虚拟结点再指向新插入的结点
    }

    // 插入一个节点到链表的尾部
    public void addAtTail(int val) {
        Node newNode = new Node(val);
        Node cur = dummyHead;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }

    // 打印链表
    public void printList() {
        Node cur = dummyHead.next; // 从虚拟头节点的下一个节点开始
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}